package hot_100;

import java.util.ArrayList;
import java.util.List;

public class 螺旋矩阵 {
    public static void main(String[] args) {

    }

    public List<Integer> spiralOrder(int[][] matrix) {
        int[][] fang = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        List<Integer> ans = new ArrayList<>();
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] vis = new int[n][m];
        int cnt = n * m;
        int x = 0, y = 0;
        int j = 0;
        while (cnt > 0) {
            vis[x][y] = 1;
            cnt--;
            ans.add(matrix[x][y]);
            while (cnt > 0) {
                int dx = x + fang[j][0], dy = y + fang[j][1];
                if (dx >= 0 && dx < n && dy >= 0 && dy < m && vis[dx][dy] == 0) {
                    x = dx;
                    y = dy;
                    break;
                } else {
                    j = (j + 1) % 4;
                }
            }
        }
        return ans;
    }
}
